package com.hc.programming.number;

import com.hc.programming.util.ArrayUtil;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 * * 0 <= a, b, c, d < n
 * * a、b、c 和 d 互不相同
 * * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 * <p>
 * 示例 1：
 * 输入：nums = [1,0,-1,0,-2,2], target = 0
 * 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 * 示例 2：
 * 输入：nums = [2,2,2,2,2], target = 8
 * 输出：[[2,2,2,2]]
 * <p>
 * 提示：
 * 1 <= nums.length <= 200
 * -10^9 <= nums[i] <= 10^9
 * -10^9 <= target <= 10^9
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/26 20:44
 */
public class 四数之和 {
    public static void main(String[] args) {
        System.out.println(ArrayUtil.toString(fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0)) + "---[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]");
        System.out.println(ArrayUtil.toString(fourSum(new int[]{2, 2, 2, 2, 2}, 8)) + "---[[2,2,2,2]]");
        System.out.println(ArrayUtil.toString(fourSum(new int[]{1000000000, 1000000000, 1000000000, 1000000000}, -294967296)) + "---[]");
        System.out.println(ArrayUtil.toString(fourSum(new int[]{1, -2, -5, -4, -3, 3, 3, 5}, -11)) + "---[-5,-4,-3,1]");
        System.out.println(ArrayUtil.toString(fourSum(new int[]{-483, -476, -475, -460, -450, -431, -428, -419, -410, -374, -347, -345, -311, -303, -299, -286, -278, -271, -260, -257, -240, -227, -217, -203, -196, -191, -189, -179, -171, -151, -150, -144, -134, -130, -112, -107, -97, -96, -94, -70, -62, -54, -38, -38, -23, -12, -11, -2, 2, 4, 30, 33, 38, 51, 51, 54, 69, 90, 108, 111, 112, 112, 121, 129, 163, 182, 184, 194, 198, 199, 210, 228, 229, 232, 236, 237, 249, 249, 259, 282, 303, 312, 317, 329, 329, 342, 349, 368, 375, 380, 384, 393, 420, 433, 441, 446, 460, 474, 497}, -2306)) + "---[]");

        // 测试 ArrayList 、 AbstractList 性能
        int count = 1000 * 10000;
        long start = System.currentTimeMillis();
        for (int i=0; i<count; i++) {
            absList(new int[]{1, 0, -1, 0, -2, 2}, 0);
            absList(new int[]{2, 2, 2, 2, 2}, 8);
            absList(new int[]{1000000000, 1000000000, 1000000000, 1000000000}, -294967296);
            absList(new int[]{1, -2, -5, -4, -3, 3, 3, 5}, -11);
            absList(new int[]{-483, -476, -475, -460, -450, -431, -428, -419, -410, -374, -347, -345, -311, -303, -299, -286, -278, -271, -260, -257, -240, -227, -217, -203, -196, -191, -189, -179, -171, -151, -150, -144, -134, -130, -112, -107, -97, -96, -94, -70, -62, -54, -38, -38, -23, -12, -11, -2, 2, 4, 30, 33, 38, 51, 51, 54, 69, 90, 108, 111, 112, 112, 121, 129, 163, 182, 184, 194, 198, 199, 210, 228, 229, 232, 236, 237, 249, 249, 259, 282, 303, 312, 317, 329, 329, 342, 349, 368, 375, 380, 384, 393, 420, 433, 441, 446, 460, 474, 497}, -2306);
        }
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start) + "ms");

        start = System.currentTimeMillis();
        for (int i=0; i<count; i++) {
            forAndTwoPointers(new int[]{1, 0, -1, 0, -2, 2}, 0);
            forAndTwoPointers(new int[]{2, 2, 2, 2, 2}, 8);
            forAndTwoPointers(new int[]{1000000000, 1000000000, 1000000000, 1000000000}, -294967296);
            forAndTwoPointers(new int[]{1, -2, -5, -4, -3, 3, 3, 5}, -11);
            forAndTwoPointers(new int[]{-483, -476, -475, -460, -450, -431, -428, -419, -410, -374, -347, -345, -311, -303, -299, -286, -278, -271, -260, -257, -240, -227, -217, -203, -196, -191, -189, -179, -171, -151, -150, -144, -134, -130, -112, -107, -97, -96, -94, -70, -62, -54, -38, -38, -23, -12, -11, -2, 2, 4, 30, 33, 38, 51, 51, 54, 69, 90, 108, 111, 112, 112, 121, 129, 163, 182, 184, 194, 198, 199, 210, 228, 229, 232, 236, 237, 249, 249, 259, 282, 303, 312, 317, 329, 329, 342, 349, 368, 375, 380, 384, 393, 420, 433, 441, 446, 460, 474, 497}, -2306);
        }
        end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start) + "ms");

    }

    /**
     * 两层for循环+双指针
     *
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> fourSum(int[] nums, int target) {
//        return forAndTwoPointers(nums, target);
        return absList(nums, target);
    }

    private static List<List<Integer>> forAndTwoPointers(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        long sum;
        for (int i = 0; i < n - 3; i++) {
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; // 剪枝
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; // 剪枝
                int left = j + 1, right = n - 1;
                while (left < right) {
                    sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }

    private static List<List<Integer>> absList(int[] nums, int target) {
        return new AbstractList<List<Integer>>() {
            List<List<Integer>> result;

            @Override
            public List<Integer> get(int index) {
                init();
                return result.get(index);
            }

            @Override
            public int size() {
                init();
                return result.size();
            }

            private void init() {
                if (result == null) {
                    result = forAndTwoPointers(nums, target);
                }
            }
        };
    }
}
